#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<map>
using namespace std;
#include "Graph.hpp"
#include "UnionFindSet.hpp"

void test1()
{
	char arr[] = "ABCDEFG";
	Graph<char, int, false> g(arr, 7);
	g.AddEdge('A', 'B', 1);
	g.AddEdge('A', 'D', 4);
	g.AddEdge('B', 'D', 2);
	g.AddEdge('B', 'C', 9);
	g.AddEdge('E', 'C', 3);
	g.AddEdge('E', 'G', 3);


	// g.BFS('A');
	for(size_t i = 0; i < strlen("ABCDEFG");++i)
		g.DFS(arr[i]);
	g.Print();
}

void test2()
{
	UnionFindSet<int> ufs(10);
	ufs.Union(8, 9);
	ufs.Union(7, 8);
	ufs.Union(6, 7);
	ufs.Union(5, 6);
	ufs.Union(4, 5);
	ufs.Union(3, 4);

	ufs.FindRoot(9);
}

void test3()
{
	const char* str = "abcdefghi";
	Graph<char, int,false> g(str, strlen(str));
	g.AddEdge('a', 'b', 4);
	g.AddEdge('a', 'h', 8);
	g.AddEdge('b', 'c', 8);
	g.AddEdge('b', 'h', 11);
	g.AddEdge('c', 'i', 2);
	g.AddEdge('c', 'f', 4);
	g.AddEdge('c', 'd', 7);
	g.AddEdge('d', 'f', 14);
	g.AddEdge('d', 'e', 9);
	g.AddEdge('e', 'f', 10);
	g.AddEdge('f', 'g', 2);
	g.AddEdge('g', 'h', 1);
	g.AddEdge('g', 'i', 6);
	g.AddEdge('h', 'i', 7);
	Graph<char, int, false> mintree(str, strlen(str));
	// g.Kruskal();
	for (size_t i = 0; i < strlen("abcdefghi"); ++i)
	{
		int w = g.Prim(mintree, str[i]);
		cout << "最小生成树权值为：" << w << endl;
	}
}

int main()
{
	test3();
	

	return 0;
}